#pragma once

#include <algorithm>
#include <vector>

namespace solution_040
{

class Solution
{
public:
    std::vector< std::vector<int> > combinationSum2(std::vector<int>& candidates, int target)
    {
        std::sort(candidates.begin(), candidates.end());
        m_candi = &candidates;
        std::vector<int> path;
        backtrack(path, 0, target);
        return m_combs;
    }

private:
    void backtrack(std::vector<int>& path, int first, int target)
    {
        if (target == 0) {
            m_combs.push_back(path);
            return;
        }

        for (int i = first; i < (int)m_candi->size() && target >= m_candi->at(i); ) {
            path.push_back(m_candi->at(i));
            target -= path.back();
            backtrack(path, i + 1, target);
            target += path.back();
            path.pop_back();

            int j = i;
            while (i < (int)m_candi->size() && m_candi->at(i) == m_candi->at(j))
                ++i;
        }
    }

    const std::vector<int>* m_candi;
    std::vector< std::vector<int> > m_combs;
};

}  /* namespace solution_040 */
